
/*
Name: Hangyu Kuang 
PROG: train 
LANG: C++
Compile: g++ train.cpp
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

typedef pair<int, int> PII;

PII swap(const PII &a)
{
	PII tmp;
    tmp.first = a.second;
	tmp.second = a.first;
	return tmp;
}

void dfs(const vector<PII > &input, unsigned int &used, int start, int end, vector<int> &cur,
		vector<int>&ans, map<int, vector<int> > &myMap, set<unsigned int> &mySet)
{
	bool notFound = true; 

	if (mySet.count(used) != 0) {
		//already search before
		return;
	}

	mySet.insert(used);

    // seletc the one that could put in the front
	vector<int> &front = myMap[start];
    for (unsigned int i = 0; i < front.size(); i++) {
		int index = front[i];
        if (used & (1 << index)) continue;
		notFound = false;
		used |= (1<<index);
		if (input[index].first == start) {
			cur.insert(cur.begin(),-(index+1));		// -1 means need to swap the pair in the output, use 1 based index to avoid swap confusion
			dfs(input, used, input[index].second, end, cur, ans, myMap, mySet);
		} else if (input[index].second == start) {
			cur.insert(cur.begin(), index+1);
			dfs(input, used, input[index].first, end, cur, ans, myMap, mySet);
		}
		cur.erase(cur.begin());
        used ^= (1 <<index);     
    }

    // seletc the one that could put in the back 
	vector<int> &back = myMap[end];
    for (unsigned int i = 0; i < back.size(); i++) {
		int index = back[i];
        if (used & (1 << index)) continue;
		notFound = false;
		used |= (1<<index);
		if (input[index].first == end) {
			cur.push_back(index+1); 
			dfs(input, used, start, input[index].second, cur, ans, myMap, mySet);
		} else if (input[index].second == end) {
			cur.push_back(-(index+1));
			dfs(input, used, start,input[index].first, cur, ans, myMap, mySet);
		}
		cur.pop_back();
        used ^= (1 <<index);     
    }

	// get the result if could not find any possible match
	if (notFound) {
		if (cur.size() > ans.size()) {
			ans = cur;
		}
	}
	return;
}


vector<PII > getLongestTrain(vector<PII > &input)
{
    unsigned int used = 0;								// bitmap hash table for 11 - 15 input
    vector<PII > ans;
	vector<int> ans1;
	map<int, vector<int> > myMap;						 //use this map to accelereate the search
	set<unsigned int> mySet;        // use this set to avoid duplicate search 
	for (unsigned int i = 0; i < input.size(); i++) {
		myMap[input[i].first].push_back(i);
		myMap[input[i].second].push_back(i);
	}

    vector<int> cur;
	for (unsigned int i = 0; i < input.size(); i++) {
		used |= (1<<i);
		cur.push_back(i+1);
		dfs(input,used, input[i].first, input[i].second, cur, ans1, myMap, mySet);
		cur.pop_back();
		used ^= (1<<i);
	}
	for (unsigned int i = 0; i < ans1.size(); i++) {
		int index = ans1[i];
		if (index > 0)
			ans.push_back(input[index-1]);
		else 
			ans.push_back(swap(input[-index-1]));
	}
	return ans;
}


/* generate a random input  */
vector<PII > genInput(int size)
{
    vector<PII > ans;
    return ans;
}

int main(int argc, char **argv)
{
	vector<PII> input;


    cout << "-----------------Test 1--------------------" << endl;
    input.push_back(make_pair(7,1));
    input.push_back(make_pair(1,2));
	input.push_back(make_pair(4,5));
	input.push_back(make_pair(9,6));
    input.push_back(make_pair(4,7));
    input.push_back(make_pair(12,4));

	input.push_back(make_pair(7,1));
    input.push_back(make_pair(1,2));
	input.push_back(make_pair(4,5));
	input.push_back(make_pair(9,6));
    input.push_back(make_pair(4,7));
    input.push_back(make_pair(12,4));

    vector<PII > ans = getLongestTrain(input);

    cout << "-----------------Test 2--------------------" << endl;
	input.clear();



    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
